A multiprogrammed data processing system has a number of programs in memory at the same time; this permits the central processor to be shared among them. This scheme improves the overall efficiency of the computer system by getting more work done in less time. The benefits of multiprogramming are increased utilization of the central processor and high total job throughput.
The objective of multiprogramming is to have a task running at all times, in order to maximize utilization of the central processor. If there are more than one task, the rest must wait until the processor is free and can be rescheduled. Means must be provided for deciding which waiting task will next receive the service of the central processor; this is the function of the scheduling and dispatching portions of the operating system.
Many scheduling methods are known in the art, providing a plurality of queues of different priorities; tasks are assigned user-set priorities, which determine the initial queue assignment. The dispatch priority of the task is further refined in response to its behavior as it proceeds.
It has been found in practice that problems can occur when a heavily loaded system is running a mix of tasks. It is possible for certain tasks of relatively low priority, but requiring only a small amount of service from the central processor before giving up control of the central processor in order to get an input-output service ("I/O bound" task), to be prevented from obtaining such service because the central processor is preferentially assigned to a higher priority task which requires a large amount of service from the central processor before giving up control ("CPU bound" task). This is generally an undesirable condition.
It is therefore an object of the invention to provide an improved operating system means that can prevent a task having a relatively low user-set priority but having I/O bound behavior from being locked out by a task having a relatively high user-set priority but having CPU bound behavior. It is a further object of the invention to maximize the throughput of a multiprogrammed data processing system running a mix of I/O bound and CPU bound tasks.
The invention is practiced in a multiprogrammed data processing system for the execution of a plurality of concurrent tasks, having timer means, storage means, input/output means, and central processing means for controlling the data storage means and the input/output means, and providing state register means. The data storage means has means for providing signals representing operating system means for the control of the data processing system, storage elements for signals defining a master control block data structure associated with operation of the central processing means under control of the operating system means, and storage elements for signals defining a plurality of task control block data structures.
Each task control block data structure is associated with one of a plurality of concurrent tasks in the data processing system, and has an associated address value representing its location within the data storage means. Each task control block data structure provides storage elements for state signals representing a current execution state of the associated task, and a priority storage element for storing a dispatch priority signal corresponding to a dispatch priority value.
The master control block data structure provides a plurality of queue storage elements for signals representing particular address values, the storage elements identifying the head and tail of at least one chained I/O wait queue representing tasks queued for service by the input/output means, and identifying the head and tail of each of N successive chained ready queues representing tasks queued to be served by the central processing means. Each ready queue has a queue priority for such service associated with its position from O to N-1, which also defines the relative priority of the queue. We will here adopt the convention that lower numbered queues have better priority (ie, are served sooner) and higher numbered queues have worse priority (ie, are served later). The queue priorities together with the positions of the tasks within the ready queues together identify a next task.
The operating system means comprises dispatcher means, scheduler means, input/output routine means, and interrupt handling means. The dispatcher means comprises means responsive to a dispatch signal for retrieving from the ready queues, address value signals representing the location of the task control block associated with the identified next task; and means responsive to the retrieved address value signals for retrieving the state signals from the associated task control block, and placing the retrieved state signals into the central processing means state register means, thereby giving control of the central processing means to the next task.
The input/output routine means is responsive to signals from the central processing means representing a call from an executing task for service by the input/output means for placing the associated address value signals of the tail of an I/O queue; the scheduler means is responsive to the calling task dispatch priority signal representative of an old dispatch priority value for resetting the dispatch priority signal to represent a new higher dispatch priority value, and for providing the dispatch signal.
The interrupt handling means is responsive to an I/O interrupt signal representing completion of an input/output function for one of the concurrent tasks, for providing a first interrupt handling means signal; the scheduler means is responsive to the first interrupt handling means signal and to the dispatch priority signal of the task control block associated with the one task, for placing associated address value signals at the tail of a corresponding ready queue.
The data storage means further provides a time interval limiting value signal. The timer means is responsive to the dispatcher means for awaiting completion of a time interval defined by the time interval limiting value signal and commencing when the retrieved state signals are placed in the state register means, and is responsive to the completion of the time interval for providing a timer interrupt signal.
The interrupt handling means is responsive to the timer interrupt signal for discontinuing execution of the currently executing task, for retrieving the current state signals from the central processing means, for placing the state signals into the task control block storage elements of the task control block associated with the discontinued task, and for providing a second interrupt handling means signal to the scheduler means.
The scheduler means is responsive to the second interrupt handling means signal and to the discontinued task dispatch priority signal representative of an old dispatch priority value for resetting the dispatch priority signal to represent a new lower dispatch priority value, and for placing address signals associated with the task control block of the discontinued task at the tail of a the ready queue corresponding to the new dispatch priority value.
According to the present invention, the data storage means further provides at least one radius storage element providing a queue radius signal, the queue radius signals together being representative of a total number of queues M less than N. Each task control block has a queue range divider storage element providing a queue range divider signal, the divider signal being derived from a user-set priority for the associated task.
The range divider signal and the range radius signals together define for each task a subset of queues divided into upper and lower ranges, and including highest and lowest priority queues for the task, the queue subset of any concurrent task having at least one queue in common with the queue subset of any other concurrent task, providing overlapped queue subsets.
For each task, the scheduler means is additionally responsive to the queue range divider signal and the queue radius signals for placing the associated task control block address signals in a particular ready queue within the queue subset defined for the task.
Further according to the present invention, the data storage means further provides a plurality of time-slice storage elements providing a plurality of discrete time-slice values, including a shortest and a longest time-slice value and monotonically increasing therebetween. For each task, the dispatcher means is responsive to the queue range divider signal and to the queue radius signal for providing a time interval limiting value signal responsive to the shortest time-slice value when the task control block address signals are retrieved from the highest priority queue in the subset, and providing a time interval limiting value signal responsive to the longest time-slice value when the task control block address signals are retrieved from the lowest priority queue in the subset, and providing time interval limiting value signals responsive to the monotonically increasing time-slice values corresponding to the remaining queues of the subset of monotonically decreasing priority.
In preferred embodiments, the data storage means further provides first and second time-slice value storage elements providing first and second time-slice signals, representing values of shorter and longer time-slices respectively. For each task, the dispatcher means is responsive to the queue range divider signal and to the queue radius signal for providing a time interval limiting value signal responsive to the first time-slice value signal when the task control block address signals are retrieved from a ready queue in the queue subset upper range, and providing a time interval limiting value signal responsive to the second time-slice value signal when the task control block address signals are retrieved from a ready queue in the queue subset lower range. The task range divider values and the radius values are related such that any task to be dispatched with the first time-slice value can be assigned to a queue having priority at least equal to that of the highest priority queue to which any other task to be dispatched with the second time-slice value can be assigned.
Preferably, the first time-slice represents a value of between 1/2 and 1 times the average CPU burst time of the I/O bound tasks concurrently running in the data processing system, and the second time-slice signal represents a value of between 1/2 and 1 times the average CPU burst time of the CPU bound tasks concurrently running in the data processing system.